package math;
import java.util.*;

public class Ex399 {
    class SolutionX{
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            Map<String,List<String>> demap = new HashMap<>();
            Map<String,List<String>> map = new HashMap<>();
            for (List<String> list: equations) {
                if (demap.containsKey(list.get(0))) {
                    demap.get(0).add(list.get(1));
                } else {
                    List<String> l = new ArrayList<>();
                    l.add(list.get(1));
                    demap.put(list.get(0), l);
                }
            }

            for (List<String> list: equations) {
                if (map.containsKey(list.get(1))) {
                    map.get(1).add(list.get(0));
                } else {
                    List<String> l = new ArrayList<>();
                    l.add(list.get(0));
                    demap.put(list.get(1), l);
                }
            }

            for (int i = 0; i < queries.size(); i++) {
                List<String> list = queries.get(i);
                String s1 = list.get(0);
                String s2 = list.get(1);
                if (!map.containsKey(s1) || !map.containsKey(s2)) {}
            }
            return null;
         }
    }

    //并查集
    /* 
        以分母为父节点，分子/分母为边权值，在查询时进行路径压缩
    */
    class Solution {
        class UnionFindSet {
            private int[] parent;
            private double[] weight;//权值，两个相连节点的商
            public UnionFindSet(int size) {
                this.parent = new int[size];
                this.weight = new double[size];
                for (int i = 0; i < size; i++) {
                    parent[i] = i; //初始化并查集
                    weight[i] = 1.0; //初始化为1是有原因的：因为根节点不需要除以谁，商作为权值的情况下，其设为1.0方便路径压缩
                }
            }

            //id1是被除数，id2是除数，因此id2是分母
            public void union(int id1, int id2, double val) {
                //查找根节点，并压缩路径
                int r1 = find(id1), r2 = find(id2);
                if (r1 != r2) {
                    parent[r1] = r2;
                    
                    /* 

                        weight[id1] * weight[root1] = val * weight[id2] //root1此时的根为root2，因此id1到root2的权值为等式左边
                        而id2到root2的权值为weight[2], 且id1 / id2 == val => 
                    */
                    weight[r1] = weight[id2] / weight[id1] * val;
                }
            }

            //通过id寻找其根节点，并进行路径压缩，修改路径上的权值 【**核心方法**】
            public int find(int id) {  
                int root, p;
                if ((p = parent[id]) == id) return id; //根的父节点就是自己，直接返回，无需路径压缩
                root = find(id); //递归的查找当前节点的根节点
                weight[id] = weight[parent[id]] * weight[id];
                parent[id] = root;
                return root;
            }

            public double isConnect(int id1, int id2) {
                int r1 = find(id1), r2 = find(id2);
                if (r1 == r2) {
                    //连在同一个根节点上，id1/id2就等于id1的权值 / id2的权值
                    // id1 / root == weigth[id1], id2 / root == weight[id2] => id1 / id2 = weight[id1] / weight[id2]
                    return weight[id1] / weight[id2];
                } else return -1.0; //不是同一个集合
            }
        }

        //将字符串的变量名称与一个自增的id进行编号，并查集可以使用数组作为主结构，简化复杂度
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int id = 0, idx = 0; 
            String s1, s2;
            Map<String, Integer> map = new HashMap<>(); //建立id与字符串的映射
            UnionFindSet ufs = new UnionFindSet(2 * equations.size());
            for (List<String> list: equations) {
                s1 = list.get(0);
                s2 = list.get(1);
                if (!map.containsKey(s1)) map.put(s1, id++);
                if (!map.containsKey(s2)) map.put(s2, id++);
                //将这个分子分母数对放入并查集中
                ufs.union(map.get(s1), map.get(s2), values[idx++]);
            }
            int size = queries.size();
            double[] res = new double[size];
            for (int i = 0; i < size; i++) {
                List<String> list = queries.get(i);
                s1 = list.get(0);
                s2 = list.get(1);
                Integer id1 = map.get(s1), id2 = map.get(s2);
                if (id1 == null || (id2) == null) res[i] = 1.0;
                else res[i] =  ufs.isConnect(id1, id2);
            }
            return res;
        }
        
    }
}
